package com.sfx.代码面试指南;

class Solution {
    private boolean[][] rows;
    private boolean[][] cols;
    private boolean[][][] grid;

    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    // 一个个的去尝试
                    for (int k = 1; k <= 9; ++k) {
                        //是否可以放,不能放直接continue
                        if (rows[i][k] && cols[j][k] && grid[i / 3][j / 3][k]) {
                            if (k == 9) {// 还有一种特殊的情况全都填不成了(1~9都不可以)
                                return false;
                            }
                            continue;
                        }
                        // 可以放入
                        board[i][j] = Character.forDigit(k, 10);
                        boolean flg = dfs(board);
                        if (!flg) {
                            board[i][j] = '.';
                        }
                    }
                }
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        rows = new boolean[9][10];
        cols = new boolean[9][10];
        grid = new boolean[3][3][10];
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    if (!rows[i][num] && !cols[j][num] && !grid[i / 3][j / 3][num]) {
                        rows[i][num] = true;
                        cols[j][num] = true;
                        grid[i / 3][j / 3][num] = true;
                    }
                }
            }
            dfs(board);
        }
    }
}